#include <iostream>
#include <vector>
#include <string>


class Solution {
public:
    void merge(std::vector<int>& nums1, int m, std::vector<int>& nums2, int n) {
        int i = m-1, j = n-1, k = m+n-1;
        while(i >= 0 && j >= 0) {
            if(nums1[i] > nums2[j]) {
                nums1[k--] = nums1[i--];
            } else {
                nums1[k--] = nums2[j--];
            }
        }
        // 如果nums2还有剩余元素，直接拷贝到nums1的前面；如果nums1还有剩余元素，不用管，因为本来就在nums1里面
        while(j >= 0) {
            nums1[k--] = nums2[j--];
        }        
    }
};


int main(int argc, char *argv[]) {
    Solution s;
    std::vector<int> nums1 = {1, 4, 8, 9, 0, 0, 0, 0};
    std::vector<int> nums2 = {4, 5, 12, 24};
    s.merge(nums1, 4, nums2, 4);
    for(auto i : nums1) {
        std::cout << i << " ";
    }
}
